package primary.code04_List;

/**
 * 打印两个"有序链表"的公共部分。
 * 给定的两个链表的头部head1和head2，打印出两个链表公共部分。
 * <p>
 * 思路：
 * 2个指针分别指向两个"有序链表"的头部；
 * 数据不同时，较小的节点指针向下移动；
 * 数据相同时，打印节点数据，并共同向下移动；
 * 直到任一指针为空；
 */
public class Code02_CommonNode {
    /**
     * 比较指针对应的值，相等则共同后移，否则对应值较小的指针后移
     * 当任一指针为空时停止
     *
     * @param head1
     * @param head2
     */
    private static void printCommonNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) return;
        while (head1 != null && head2 != null) {
            if (head1.data == head2.data) {
                System.out.print(head1.data + "-->");
                head1 = head1.next;
                head2 = head2.next;
            } else if (head1.data < head2.data) {
                head1 = head1.next;
            } else {
                head2 = head2.next;
            }
        }
        System.out.println();
    }

    private static void printCommonNodeTest(Node head1, Node head2) {
        while (head1 != null && head2 != null) {
            if (head1.data == head2.data) {
                System.out.print(head1.data + "-->");
                head1 = head1.next;
                head2 = head2.next;
            } else {
                if (head1.data < head2.data) {
                    head1 = head1.next;
                } else {
                    head2 = head2.next;
                }
            }
        }
    }

    private static String printList(Node head) {
        if (head == null) {
            return null;
        }
        StringBuilder sbResult = new StringBuilder();
        Node temp = head;
        while (temp != null) {
            sbResult.append(temp.data + "-->");
            temp = temp.next;
        }
        return sbResult.toString();
    }

    /**
     * 链表1：1-->2-->3-->4-->5-->
     * 链表2：3-->4-->5-->6-->7-->
     * 3-->4-->5-->
     */
    public static void main(String[] args) {
        Node node11 = new Node(1);
        Node node12 = new Node(2);
        Node node13 = new Node(3);
        Node node14 = new Node(4);
        Node node15 = new Node(5);
        node11.next = node12;
        node12.next = node13;
        node13.next = node14;
        node14.next = node15;

        Node node21 = new Node(3);
        Node node22 = new Node(4);
        Node node23 = new Node(5);
        Node node24 = new Node(6);
        Node node25 = new Node(7);
        node21.next = node22;
        node22.next = node23;
        node23.next = node24;
        node24.next = node25;

        System.out.println("链表1：" + printList(node11));
        System.out.println("链表2：" + printList(node21));
        printCommonNodeTest(node11, node21);
    }
}

